package 动态规划

/*
https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked

5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"
*/

func longestPalindrome(s string) string {
	//获取字符串长度
	n := len(s)
	if n < 2 {
		return s
	}

	maxLen, begin := 1, 0 //最长回文子串最少也是1, 开始下标先初始化为0

	dp := make([][]bool, n) // dp[i][j] 表示 s[i...j] 是否是回文串
	for i := range dp {
		dp[i] = make([]bool, n)
		dp[i][i] = true
	}

	// 注意: 先填左下角
	for j := 1; j < n; j++ {
		for i := 0; i < j; i++ {
			if s[i] != s[j] {
				dp[i][j] = false
			} else {
				if j-i < 3 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
			}

			// 只要 dp[i][j] == true 成立, 就表示子串 s[i...j] 是回文, 此时记录回文长度和起始位置
			if dp[i][j] && j-i+1 > maxLen {
				maxLen = j - i + 1
				begin = i
			}
		}
	}

	return s[begin : begin+maxLen]
}
